home *** CD-ROM | disk | FTP | other *** search
/ Freaks Macintosh Archive / Freaks Macintosh Archive.bin / Freaks Macintosh Archives / Textfiles / zines / Phrack / Phrack Issue 53.sit / 53 / P53-05 < prev    next >
Text File  |  1998-07-08  |  49KB  |  867 lines
  1. ---[  Phrack Magazine   Volume 8, Issue 53 July 8, 1998, article 05 of 15
  2.  
  3.  
  4. -------------------------[  Introduction and Overview of Internet Routing
  5.  
  6.  
  7. --------[  krnl <krnl@heuristic.org>
  8.  
  9.  
  10.  
  11. ----[  Routing Overview: 
  12.  
  13. The process of routing can be quickly summarized as a node finding the path to
  14. every possible destination.  Routing is present in everything from layer 1
  15. (the physical layer) on up.  The routing that most people are familiar with,
  16. however, occurs at layer 3 (the network layer) and as such, we will only
  17. reference layer 3 (and more specifically) Internet Protocol (IP) routing in
  18. this document.
  19.  
  20. Protocols for exchange of routing information connect multiple routers around
  21. the world to provide them with a common view of the network through their
  22. heterogeneous, though generally consistent routing tables.  Routing tables
  23. store all information necessary for the router to reach every destination on
  24. the network irrespective of size (i.e. the network could be j.random LAN with
  25. one ip router and two hosts off of an ethernet port or it could be the
  26. Internet proper).
  27.   
  28. ----[  Routing Protocols: 
  29.  
  30. There are a wide variety of routing protocols used to contribute to the
  31. routing tables across a network.  Protocols such as BGP, OSPF, RIP and ISIS
  32. help to convey a correct and coherent picture of the network to all network
  33. switches (routers). 
  34.  
  35. ----[  Routing Goals: 
  36.  
  37. You can imagine that if each router has to store information that would allow
  38. it to reach every destination on the network, there is the possibility for it
  39. to amass a large routing table.  Large routing tables are difficult (and
  40. sometimes impossible) for routers to process because of physical constraints
  41. (cpu, memory or a combination).  Therefore, we would like to minimize the
  42. routing table space without sacrificing the ability to reach every destination
  43. on the network.  For example, if the router is connected to the Internet via
  44. one DS1 link to another router, the router could store routing table
  45. information for each destination on the Internet or it could just default
  46. non-local information out that serial link.  What defaulting means is that if
  47. the router does not have a specific entry in its table for the destination
  48. that the packet is trying to find, it sends it out the default link.  The
  49. router towards which a router sends defaulted packets is sometimes called the
  50. 'gateway of last resort'.  This simple trick allows many routing tables to
  51. save a number of entries on the 30th order of magnitude.  Routing information
  52. should not be exchanged between routers in a spurious fashion.  Frequent churn
  53. in the routing table puts unnecessary stresses on the scare memory and cpu of
  54. any given router.  Information propagation should not interfere with the
  55. forwarding operations of the router.  Though this means that you should not
  56. send routing updates every nanosecond, it does not mean that routing
  57. information should only be exchanged and updated weekly.  One of the important
  58. goals of routing is that it provide the host with a table which accurately
  59. reflects the current status of the network. 
  60.  
  61. The most important aspect of a router's operation is sending packets from
  62. input to correct output.  Misrouting packets could cause a loss of data.
  63. Routing table inconsistencies could also cause routing loops whereby a packet
  64. is passed between two adjacent interfaces ad infinitum. 
  65.  
  66. It is desirous for routers to have quick convergence.  Convergence can be
  67. informally defined as a metric which gauges the speed at which routers arrive
  68. at a consistent view of the network.  It would be ideal to have infinitesimal
  69. convergence times because that would ensure that each router on the network
  70. can accurately reflect the current topology even after a drastic change (link
  71. failure).  When the network is changing, each router must propagate data which
  72. will aid other routers in converging to the correct picture of the network
  73. status.  Problems with quick convergence are found in the routing updates.  If
  74. a link is flapping (changing line status from up to down) rapidly, it can
  75. generate numerous installation and withdrawal requests.  Therefore, that one
  76. link can end up consuming the resources of every router on the network because
  77. the other routers are forced to install and withdraw the route in rapid
  78. succession.  While convergence is an important goal of routing protocols, it
  79. is not a panacea to network woes.
  80.  
  81.   
  82. ----[  Distance Vector Routing
  83.  
  84. Distance vector routing protocols distribute a list of <destination, cost>
  85. tuples to all of the router's neighbors.  These tuples assign a cost to reach
  86. every other node of the network.  It is important to note that this routing
  87. information is only distributed to routers which are assigned as neighbors to
  88. the originating router.  These neighbors are often physical, but can be
  89. logical in the case of eBGP multihop.  That cost is the sum of the link costs
  90. for the router to reach a destination.  Routers periodically send their
  91. neighbors distance vector updates; the neighbor then compares the received
  92. distance vector to its current distance vector.  If the received values are
  93. lower, the router sends output to the destination in the distance vector over
  94. the link that it received the vector over. 
  95.  
  96. The count to infinity problem is a problem with many distance vector
  97. implementations.  We will assume that all links have a unit cost and that each
  98. hop corresponds to a unit.  For example, if router X is connected to router Y
  99. and router Y is connected to router Z, we can demonstrate this problem (see fig
  100. 1).  Y knows a 1 hop path to Z and X knows a 2 hop path to Z.  Assume that
  101. link YZ goes down and the cost of that route is increased to infinity (fig 2).
  102. Now, Y knows an infinite cost route to Z because it knows the link is down so
  103. it propagates this distance vector to X.  Suppose X has sent an update to Y
  104. which advertises a 2 hop distance vector.  Now, Y will think that it can get
  105. to Z through X, so it sends X an update that says it can get to Z in three
  106. hops (fig 3).  Note that X has no idea that the distance vector being
  107. advertised to it was originated from X.  This is a serious flaw in distance
  108. vectors.  In their unmodified form, they do not contain the full path
  109. information that the route has traversed.  As illustrated above, the router
  110. alternates states of advertising a path to Z and advertising infinity to Z.
  111. They keep this exchange up forever or until they have reached some internally
  112. defined infinity count (say 15 as in the case of RIP).
  113.  
  114. Count to Infinity problem:
  115.  
  116.           X--------------------Y--------------------Z
  117.  
  118.          Y:1                  X:1                  X:2
  119.          Z:2                  Z:1                  Y:1
  120.  
  121.                             [ fig 1 ]
  122.     All links are up, below each node we note the destination and hopcount
  123.     from each respective node.
  124.  
  125.  
  126.           X--------------------Y--------* *---------Z
  127.  
  128.          Y:1  <-------------  Z:infinity
  129.          Z:2  ------------->  X:1
  130.  
  131.                             [ fig 2 ]
  132.     The link Y - Z breaks.  Node X advertises Z:2 to node Y.
  133.  
  134.  
  135.  
  136.           X--------------------Y--------* *---------Z
  137.  
  138.          Z:infinity(frm Y) -> X:1
  139.          Y:1  <-------------  Z:3
  140.  
  141.                             [ fig 3 ]
  142.     Node Y sends its Z distance vector to X _before_ it recieves node X's
  143.     infinity.  Once node Y receives node X's infinity, it sets its distance to
  144.     infinity.
  145.  
  146. A path vector is an easy way to defeat the count-to-infinity problem.
  147. Basically, each distance vector also includes the router path that it
  148. traversed (fig 4).  The router rejects an update from its neighbor if the path
  149. included in the update includes the router receiving the update (fig 5).  The
  150. Border Gateway Protocol (which is used to exchange routing information between
  151. Autonomous Systems on the Internet) incorporates the path vector to stop the
  152. count-to-infinity problem.  Obviously, you have to incorporate more
  153. information in the routing table if you want to include the AS path
  154. information that the route has traversed.  The designers of BGP decided that it
  155. was optimal to sacrifice storage space and processing power for the robustness
  156. that the path vector affords the routing protocol. 
  157.  
  158. Path Vector Solution: 
  159.  
  160.           X--------------------Y--------------------Z
  161.  
  162.          Y:1 (Y)              X:1 (X)              X:2 (YX)
  163.          Z:2 (YZ)             Z:1 (Z)              Y:1 (Y)
  164.  
  165.                             [ fig 4 ]
  166.     All links are up, below each node we note the destination, hopcount and
  167.     path vector from each respective node.
  168.  
  169.  
  170.           X--------------------Y--------* *---------Z
  171.  
  172.          Y:1 (Y)              X:1 (X)
  173.          Z:2 (Y Z)            Z:infinity
  174.  
  175.                             [ fig 5 ]
  176.     The link Y - Z breaks.  Node Y knows to ignore Xs advertisement of Z 
  177.     because Y is the path vector.  The avoids the count-to-infinity problem.
  178.  
  179.  
  180. Another way to counter this problem is the split horizon.  Basically, this
  181. means that a router shouldn't advertise a path to a neighbor if that neighbor
  182. is the next hop to the destination.  This solves the problem presented in the
  183. example above because the path to Z from X through Y would not have been
  184. advertised to Y because Y is the neighbor _and_ the next hop to the
  185. destination (Z).  A variation called split horizon with poisonous reverse has
  186. router X advertise an infinite cost to get to destination Z.  Under a split
  187. horizon, router X would not advertise that it could get to router Z.
  188.  
  189.  
  190. ----[  Link State Routing
  191.  
  192. A router using a link state routing protocol distributes the distance to its
  193. neighbors to every other router on the network.  This allows each router on
  194. the network to make a routing table without knowing the full cost to the
  195. destination from any one source.  The problems of loops are avoided because
  196. each router contains the full topology of the network.  Basically, the router
  197. makes a 3 tuple containing the source router (itself) the neighbor and the
  198. cost to its neighbor.  Therefore, if router A is connected to Router B over a
  199. link of cost 3 and router A is connected to router C over link cost 5, then
  200. router A would advertise the Link State Packets (LSPs) <A,B,3> and <A,C,5> to
  201. all routers on this network.  Each router on the network would evaluate all of
  202. the LSPs that it receives and calculate a shortest path to every destination
  203. on the network. 
  204.  
  205. Obviously, the LSP is an integral part of the convergence process.  If someone
  206. could inject false LSPs into the network, it could result in misrouted
  207. information (a packet taking a longer path than it should) or even in the
  208. blackholing of a router on the network.  This is not necessary a malicious
  209. attack of a network, however.  Router C could advertise a link to its neighbor
  210. D with the 3 tuple <C,D,6> and then withdraw the announcement when the link
  211. goes down.  Unfortunately, if the LSP advertising the link having an infinite
  212. cost arrives before the LSP advertising the cost of that link being 6, the
  213. routing table will not reflect the topology of the network and will be in that
  214. state until another LSP comes to correct the problem. 
  215.  
  216. To combat this, a sequence number is introduced into the LSP.  Therefore, all
  217. of the routers on the network would initialize their sequence number to some
  218. starting value and then start advertising their LSPs.  This solves the above
  219. problem in that the LSP advertising the link of infinite cost would have a
  220. higher sequence number than the LSP advertising the link as having cost 6.
  221.  
  222. Some problems encountered when using sequences numbers are finite sequence
  223. space, sequence initialization, and aging.  It is in the best interest of a
  224. robust link state protocol needs to protect its LSPs as well as choose a
  225. sequence space which is sufficiently large to accommodate updates.  The
  226. sequence space that the LSPs can use is set to some finite value.  Therefore,
  227. when the sequence numbers reach the top of the space, they must wrap around
  228. towards the smallest sequence number.  This presents a problem because when a
  229. router compares link state updates, the greater sequence number takes
  230. preference.  To combat this problem, you can define a maximum age of the LSP.
  231. Therefore, if you have not received an update in X ticks, you discard the
  232. current LSP information and wait for a further update.  It must be noted that
  233. this invalidates the path information to a destination.  For example, if
  234. router Y advertises a cost to its neighbor router Z where router Y is
  235. connected by one link to a meshed network, when the link between the mesh and
  236. router Y breaks, the other routers in the mesh have preserved link state
  237. information that will allow them to find a path towards Z.  If they receive no
  238. updates in MAX_AGE, then they will assume that the link to Y is unreachable.
  239. This will allow each router to converge its table and allow it to advertise an
  240. infinite LSP for Y and Z. 
  241.  
  242. Sequence initialization is also an important facet of this problem.  Say
  243. router Y crashed and is rebooting while the network is recalculating paths to
  244. it.  When it starts its link state protocol back up, it must somehow indicate
  245. that it needs to reinitialize its sequence number to the last number it gave
  246. all of the other routers to allow for coherence.  Therefore, it can announce
  247. paths with a sequence number in a special "initialization set".  This
  248. initialization set will tell the other routers that this router needs the
  249. sequence where it left off.  This is the "lollipop sequence" idiom.  The
  250. sequence space really resembles a lollipop in that the normal sequence number
  251. keep churning around the finite sequence space while reinitialization takes
  252. place in a short linear sequence space (comparable to the stick :).
  253.  
  254. Great pains are taken to ensure the integrity of LSPs.  In fact, this entire
  255. routing algorithm depends on the LSP being digested in a coherent method to
  256. guarantee that each router has the correct view of the network topology.  The
  257. question still remains how the root node router computes the distance to each
  258. destination. 
  259.  
  260. Because of the general nature of a link state protocol, you have various nodes
  261. of the network advertising the distance to get to their neighbors to every
  262. other node on the network.  Thus each node has a collection of neighbor
  263. distances from various routers on the network.  The routing table is basically
  264. 'grown' outward from the root node to all of the network extremities.  This
  265. will be explained in a slightly rigorous fashion in the next section.
  266.  
  267.  
  268. ----[  Dijkstra's Algorithm
  269.  
  270. This algorithm is a simple and elegant way to determine network topology.
  271. Basically, there are two distinct sets of destinations on the network.
  272. Destinations in set K are known routes for which a shortest path has been
  273. computed.  Destinations in set U are routers for which the best path to that
  274. router is not currently known.  In this set, paths are being considered as
  275. candidates to be the best path to that destination. 
  276.  
  277. To start off, add the current node p into the set K.  Then add all of its
  278. neighbors into the set U with path/cost associations.  If there is another path
  279. to one of the neighbors in the U set, then choose the path which costs the
  280. least.  When the neighbors N* are added to U make sure that they indicate the
  281. cost through p as well as p's ID . 
  282.  
  283. Once this has been done for the set U, then pick the neighbor n to p which has
  284. the smallest cost to reach p.  This is assuming that the neighbor has not
  285. already been installed in K.  This algorithm stops when set U is equivalent to
  286. the empty set.  When set U is null, it is implied that all destinations are in
  287. set K and have the shortest cost from the root node P on which this algorithm
  288. is running.  Note, that each step evaluates adds ONE neighbor into K. That
  289. neighbor is the router with the smallest cost to reach p. 
  290.  
  291.  
  292. ----[  Distance Vector vs. Link State
  293.  
  294. We are left with these protocols like BGP which uses path vector and OSPF
  295. which uses link state.  Why do they occupy such orthogonal space?  When a link
  296. state protocol is working correctly, it guarantees that there will be no
  297. routing loops in the network. The link state protocol also guarantees fast
  298. convergence when there is a change in the topology of the network because the
  299. link state is distributed on a flat routing space.  Since link state protocols
  300. contain these inherent advantages, why do protocols like BGP chose to employ
  301. the path vector approach? 
  302.  
  303. Taking a cross-section of routing protocols that are employed on the internet,
  304. one finds that the majority of large providers use OSPF to resolve routing
  305. information on their internal network and BGP to talk to other distinct
  306. networks (or autonomous systems) at their borders of administration.  What
  307. suits BGP as an external protocol and OSPF for an internal routing protocol? 
  308.  
  309. One issue, which will be discussed in the next section, is hierarchy.  BGP
  310. provides a mechanism for a routing hierarchy which enables it to greatly
  311. reduce the space of its table.  OSPF, which is a link state protocol,
  312. provides a flat routing table whereby any internal router knows the full
  313. hop by hop path to any destination within the autonomous system.  Furthermore,
  314. distance vector protocols understand that different areas can have different
  315. views of the network where link state protocols require that each node
  316. independently compute a consistent view of the network.  This saves the DV
  317. protocol the overhead of maintaining a correct LSP database.  BGP also has
  318. another 'advantage' in that it is layered on top of the Transmission Control
  319. Protocol (TCP).  Therefore, in the 'best-effort' service of IP networks, BGP
  320. has assurance (to the level that TCP can guarantee) that routing information
  321. will be propagated.  Whereas, you can (or should) be able to govern the status
  322. of your internal network, the nebulous exterior past your border routers
  323. confers no delivery guarantee on your routing information.  
  324.  
  325. Each type of routing algorithm is suited for its function.  Link State
  326. protocols provide the quick convergence that is essential to an internal
  327. network while distance vector protocols provide external reachability.
  328. Hierarchy is not something that is inherent in distance vector protocols,
  329. but the implementation of a hierarchy has made BGP a widely used exterior
  330. gateway protocol.
  331.   
  332.  
  333. ----[  Routing Hierarchy
  334.  
  335. Routing hierarchy is an oft fought debate that borders on religion.  There
  336. are constantly questions about how hierarchy should be implemented (if at
  337. all) in the free form state of the current global network.  Hierarchy imposes
  338. a tree of authority with the overall authority at the top of the tree and
  339. branching down to regional authorities, local authorities ad infinitum.
  340. Hierarchy simplifies routing because if a destination is not locally routable
  341. (or under your section of the tree).  You can iterate up towards the top tree
  342. to try and deliver that information.  As you move towards the top, the routing
  343. information contained in the routers becomes less and less specific until you
  344. reach the root node which is the least specific.  It does, however, know how
  345. to route information to every possible destination on the network.  It may help
  346. you to envision the hierarchy of the telephone network (built under one
  347. collective).  If a call cannot be placed within a central office, it is handed
  348. to either another central office in the area code or a wide area link.  The
  349. wide area link understands how to route to each area code in a full national 
  350. mesh whilst the local 5ess switch only knows routing information for more
  351. specific prefixes.  As the phone number becomes less specific (from right
  352. to left), the routing decision moves further up the strict hierarchy.
  353.  
  354. This similar to how the domain name system (DNS) works on the internet (fig 6).
  355. You provide local records for domains that you host.  When your nameserver
  356. receives a query for a record, it either returns the fact that it has
  357. authority for that record or points toward the root nameserver.  The root
  358. nameserver knows the delegations of .com, .net, .org et al. and then points
  359. towards the site responsible for that top level domain.  That site then points
  360. towards the site that has authority for the specific second level domain.
  361. Domain names take the form of most specific -> least specific; i.e.
  362. microsoft.com is more specific than just .com.  Likewise
  363. gates.house.microsoft.com is more specific than microsoft.com.
  364.  
  365. DNS Hierarchy: 
  366.                             ___ . ___
  367.                            /    |    \
  368.                       .com.   .org.   .edu. 
  369.                          /      |      \
  370.            microsoft.com.    eff.org.   isi.edu. 
  371.                        /        |        \
  372.    billy.microsoft.com.    x0r.eff.org.   rs.isi.edu. 
  373.  
  374.                             [ fig 6 ]
  375.     Each level in the hierarchy is responsible for levels of greater
  376.     specificity.
  377.   
  378. Root authority is controlled by the Internet Assigned Numbers Authority
  379. (IANA).  It provides the top of the hierarchy in a "centrally" managed
  380. database (in fact, there are multiple root servers distributed across the
  381. county which maintain a consistent database).  This is the closest example of
  382. strict hierarchy that can be found on the internet. 
  383.  
  384. With IP addresses, specificity increases in the opposite direction.  IP
  385. addresses (version 4) are 32-bits.  The rightmost bit signifies the greatest
  386. amount of specificity and the leftmost, the least.  IP routing authority
  387. information is not maintained in a centralized database.  Routing information
  388. is exchanged between autonomous systems via the BGP protocol.  Routes take
  389. preference in order of most specific -> least specific.  In this way, there is
  390. some type of hierarchy in the system (even though it is more loose than the
  391. DNS example).  Generally, larger providers control larger parts of the total
  392. IPv4 space ((2^32) - 3 addresses).  The converse is also true. 
  393.  
  394. Classless Inter-Domain Routing (CIDR) also helped to decrease the size of
  395. routing tables and increase the appearance of hierarchy.  Now, instead of
  396. Sprint announcing routes to 130.4.0.0 through 130.20.0.0 (on the classical B
  397. space boundary) it could announce 130.4.0.0/12 which encompasses that entire
  398. 16 class B range.  The classful ranges, subnetworking and the like are
  399. discussed in my "introduction to IP" page and are therefore not included in
  400. this document. 
  401.  
  402.  
  403. ----[  Routing Hierarchy and Aggregation
  404.  
  405. BBN divides their 8/8 network into two subnetworks and advertises reachability
  406. to the aggregate to save table space.  Once inside an AS, routing obeys a fairly
  407. strict hierarchy.  Router A is responsible for the entire 131.103/16.  It
  408. divides it into two /17. Likewise, Router D in AS1 is responsible for 8/8 and
  409. chooses to divide it into 8.0/9 and 8.128/9 and divides responsibility for
  410. these networks to Routers E and F respectively (fig 7).  Routers B, C, E, and F
  411. can further choose to subdivide their networks in a hierarchical fashion.
  412. Because of the binary nature of subnetting, networks can only be divided in
  413. half.
  414.  
  415. Routing Hierarchy and Aggregation:
  416.  
  417.                                        BGP
  418.  
  419.                 131.169.0.0/16  <-------------------->  8.0.0.0/8
  420.                       A (AS1239)                        D (AS1) 
  421.                     /   \                             /   \
  422.                  B /     \ C                       E /     \ F
  423.                   /       \                         /       \
  424.      131.169.0.0/17       131.169.128.0/17      8.0/9       8.128/9
  425.  
  426.                             [ fig 7 ]
  427.     In the internet, there is no strict routing hierarchy.  There are simply
  428.     large networks which peer via BGP to distribute aggregated routing
  429.     information.
  430.  
  431.  
  432. The national backbone is populated by few nodes (when compared to the end
  433. nodes).  Most national providers are one or two router hops away from every
  434. large network.  Through aggregation in networks below, national providers
  435. provide fully (or at least we hope) aggregated routing information.  In a
  436. strict hierarchy, only one router on any given hierarchy level can advertise
  437. reachability to a specific portion of the network.  In the current state of
  438. the Internet, multiple routers can advertise reachability information.  For
  439. example, Sprint announces 131.169.0.0/16 out to Digex, MCI, and BBN.  Though
  440. this breaks some of the benefits of a strict hierarchy, it confers other
  441. benefits.  This scheme allows for distributed control of routing information
  442. instead of depending on the node above.  Also, nodes on the same level are
  443. often interconnected to aid in the dissemination of routing information.
  444.   
  445.  
  446. ----[  Aggregation
  447.  
  448. As discussed slightly before, aggregation allowed the internet to reduce the
  449. size of its external reachability tables.  Before, the granularity of route
  450. announcements allowed for only /8, /16, and /24 (octet boundaries).  Now, with
  451. CIDR you could use variable length subnet masks.  The only requirement was
  452. that they fall on one of the 32-bit boundaries of the IP address.
  453.  
  454. Classless routing not only allows us to minimize routing table space, it also
  455. allows us to divide up large chunks of unused space into manageable pieces.
  456. Much of the Class A space is terribly under-utilized.  With this scheme one
  457. can more efficiently allocate IP addresses to providers/netizens. The American
  458. Registry of Internet Numbers (ARIN) controls the allocation of IP addresses
  459. within the United States.
  460.  
  461. Aggregation helps alleviate the problems of not being in a strict hierarchical
  462. structure.  It allows the least amount of route table specificity at each
  463. level (assuming the routers on that level choose to fully aggregate their
  464. announcements.)  The less specific aggregates do not necessarily indicate the
  465. position of a router in the hierarchy.  For example, a university may announce
  466. a /8 and be 3 hops away from the national backbone. 
  467.  
  468. A problem with aggregates can be found when we examine candidate route
  469. specificity.  If ISP A only has address space from within the allocated block
  470. to their parent P, then aggregation could cause problems if ISP A wanted to
  471. multihome to parent Q.  The problem comes in that ISP A is obligated to
  472. advertise reachability only to their space.  This would constitute them
  473. announcing their address space to Parent Q.  Assume that parent P aggregates
  474. ISP A's space into a /16 for the sake of saving route announcements.  Now, ISP
  475. A would seem to have better reachability only through parent Q because of the
  476. specificity of the route announcement (remember that more specific routes take
  477. precedence over less specific routes).  This would nullify the benefits of
  478. multihoming in an attempt to distribute load over the two lines.  In this case,
  479. ISP A would ask parent P to announce a more specific destination which has a
  480. length matching the length of the aggregate assigned to ISP A.  Therefore, to
  481. the world above parent P and parent Q, the path to ISP A looks equally
  482. appealing. 
  483.  
  484.  
  485. ----[  Exterior/Interior
  486.  
  487. It is important to look at how routing information is disseminated throughout
  488. the network.  It has already been discussed that we use separate routing
  489. protocols (with their respective benefits/costs) to talk to the internal and
  490. external world.  However, these protocols cannot take orthogonal views on
  491. routing information.  In fact, the interplay between interior and exterior
  492. routing protocols is what allows data to be effectively relayed to a
  493. destination external to the network as well as to distribute external routing
  494. information to all nodes on the internal  network. 
  495.   
  496. There are a few ways to ensure that each router has a consistent view of the
  497. network.  One is to distribute the external protocol into the internal
  498. protocol.  Thereby, the internal protocol instantly has routing information
  499. injected in it for the best path to every external destination.  Note that the
  500. router which talks eBGP (or comparable protocol) only redistributes the route
  501. that it installs in its routing table and not the other candidate routes which
  502. may have been advertised to it. 
  503.   
  504. Another approach is to inject the interior protocol into the exterior protocol.
  505. Of course, this necessitates filtering at the entrance point to the exterior
  506. protocol to prevent the announcement of all internal specifics.  You can
  507. accomplish internal routing dissemination inside an Interior Gateway Protocol
  508. mesh.  Because of the specifics of protocols like BGP, externally learned
  509. routing information will only be propagated one logical hop within the network.
  510. Therefore, every router that must know this external reachability information,
  511. must be fully meshed with the eBGP speaking routers.  Also, if other routers
  512. are injecting information into the Exterior Gateway Protocol, the router
  513. should be logically fully meshed with them. 
  514.   
  515.  
  516. ----[  Multicast Routing Overview
  517.  
  518. What we have been talking about above is unicast routing.  In unicast routing,
  519. you assume that each packet has a single destination address.  Assuming
  520. infinite resources being available, unicast is a feasible solution for every
  521. situation.  However, there are situations when it would be advantageous to send
  522. a packet to multiple destinations from a single source (point to multipoint) or
  523. from multiple sources to multiple recipients (multipoint to multipoint).
  524.  
  525. The point of multicast is to provide a multicast group to which hosts can
  526. subscribe and get the specific multicast feed.  The multicast group is a single
  527. IP address in class D space.  Therefore, the senders and receivers are only
  528. associated by a given multicast group address.  Thus, the senders move their
  529. data towards the multicast group address and the receivers specify that they
  530. want to receive information from a given group address.  In fact, the sender
  531. is not required to know any information about the hosts that are receiving the
  532. feed. 
  533.  
  534.  
  535. ----[  Multicast vs. Unicast
  536.  
  537. If one was sending packets from a single source to a set of destinations, it
  538. is important to investigate how multicast and unicast handle the distribution. 
  539.  
  540. Assume that router A is sending data to routers B, D and E.  A is at the top of
  541. the hierarchy, B and C are at the second level of the hierarchy, and D and E
  542. are below router B.  With multiple unicast (fig 8), router A makes 3 copies of
  543. the packet and sends them down link AB.  Router B then sends one packet to a
  544. host off of its ethernet and forwards the last two packets to routers D and E
  545. whereupon those routers send the packets to the their respective hosts in the
  546. multicast group. 
  547.  
  548. Therefore, this transmission takes up 3 packets per second on link AB and 1
  549. pps on links B->Host(b), router D and router E.  In a multicast routing
  550. implementation, assuming the same topology, we will have less packets.  The
  551. difference is that router A sends _one_ packet over link AB.  Router B then
  552. triplicates the packet and sends it to Host(b), router D and router E (fig 9).
  553. One way for triplicating the packet is to simultaneously close crossbars on a
  554. fully crossed switch fabric, thus sending data from one input to three outputs
  555. simultaneously.  As long as there is route redundancy, multicast is very
  556. efficient because it minimizes redundant packets traveling to the same
  557. next-hop.  Simply, as long as there is route redundancy for the distributed
  558. session (for example, an audio feed) you will see an advantage with multicast
  559. over unicast. 
  560.  
  561. Multicast Overview Example:
  562.  
  563.         Multiple Unicast:
  564.                         A           A sends 3 packets to B.
  565.                        / \
  566.                       /   \ 3
  567.                      /     \
  568.                     C       B       B sends 1 packet to each to D and E.
  569.                            / \
  570.                         1 /   \ 1
  571.                          /     \
  572.                         D       E   D and E send 1 packet to their respective
  573.                                     hosts. 
  574.  
  575.                             [ fig 8 ]
  576.  
  577.         Multicast:
  578.                           
  579.                         A           A sends 1 packet to B
  580.                        / \
  581.                       /   \ 1
  582.                      /     \
  583.                     C       B       B duplicates the packet for its host; 
  584.                            / \      therefore, there is 1 packet (at most) on 
  585.                         1 /   \ 1   each link.
  586.                          /     \
  587.                         D       E
  588.  
  589.                             [ fig 9 ]
  590.  
  591.  
  592. This is a multicast topology rooted at node A.  There is also a shortest path
  593. from A to every destination in the multicast group.  This is called the
  594. shortest path multicast tree rooted in A.  Data would like to shortest path on
  595. the network layer.  One problem with multicast sessions is that recipients
  596. join and leave during a multicast session.  This requires pruning of the
  597. multicast "tree" so that packets do not clutter a link on which there is no
  598. one requesting data from a given multicast group.
  599.  
  600. To detect if there are hosts on a particular broadcast LAN that are interested
  601. in a multicast group, the router sends out Internet Group Management Protocol
  602. (IGMP) messages.  Each packet has a random reply time from which the host will
  603. express interest.  This is to prevent all hosts on a broadcast LAN from
  604. responding at the same time to an IGMP query.  Once one host desires to
  605. receive data destined for a particular multicast groups, all other hosts which
  606. desire to be in the multicast group can discard their replies because the
  607. router knows to multicast all incoming packets destined for that group.  The
  608. host then configures its adapter to answer for the MAC address corresponding
  609. to that group. 
  610.  
  611. Multicast must also be functional outside of the broadcast LAN.  A simple
  612. solution to the problem is to give each router for which multicast is enabled
  613. the multicast packet.  This is called flooding.  Basically, it functions by
  614. forwarding the packet to every interface other than the one that the packet
  615. arrived on.  The inherent flaws in this approach is that there is packet
  616. duplication as well as packets being sent to routers which have no hosts
  617. subscribed to the multicast group.  To clarify the duplication statement, if
  618. Router A is physically meshed with routers B, C, and D and linked to its
  619. upstream via serial, when router A receives the multicast packet, it floods it
  620. out the interfaces to routers B, C, and D.  These routers then flood the packet
  621. out the interface other than the one they received the packet on (namely the
  622. interface that connects them to A).  This results in each of these routers
  623. receiving two copies of the packet (other than the one they received from A)
  624. in this exchange.
  625.  
  626. A solution to this problem can be found in a technique called Reverse Path
  627. Forwarding (RPF).  RPF specifies that the router forwards a packet with a
  628. source address of X only if the interface which the router receives the
  629. packet on corresponds to the shortest path that router has to source
  630. X (fig 10).  Therefore, in the above example, each of the meshed routers
  631. _still_ receives 2 duplicate packets in the second step, but they refuse to
  632. forward them because only the packet received from the interface directly
  633. connected to A will be forwarded.  As noted, RPF does not completely solve
  634. the problem of packet duplication.  To solve this, we must introduce
  635. pruning.  The idea is simplistic: inform neighbors that you do not wish to
  636. receive multicast packets from source X to multicast group Y.  You can also
  637. specify prunes to a particular group.  If a router tells its neighbors that it
  638. did not desire to receive packets for group Y and then has a host which
  639. desires to receive group Y, it sends a graft message to its neighbors
  640. specifying that it be added into the multicast tree.
  641.  
  642. As a unicast aside, RPF can also be used to eliminate source address spoofing
  643. in that the router will only forward packets from source Y if it is receiving
  644. it on the interface which is the shortest path to source Y.  Thus, if the
  645. router receives packets from an external link which say their saddr ==
  646. saddr(y), the router will not forward them because its shortest path to Y is
  647. not from the external link. 
  648.  
  649. RPF Example:
  650.  
  651.                     | <-- Point of ingress.
  652.                     |
  653.                     A-----------C
  654.                     |\         /|
  655.                     | \_______/ |
  656.                     | /       \ |
  657.                     |/         \|
  658.                     B-----------D
  659.  
  660.                             [ fig 10 ]                  
  661.     ABCD are physically meshed.  When A distributes a packet to BCD, there is
  662.     no problem.  Now, in the next step, B, C,and D forward the packet to each
  663.     of their respective neighbors (for B it would be C and D and ! A because
  664.     it received the packet from A).  This results in C and D receiving 2
  665.     packets in this entire exchange.  Note that C and D now do _not_ forward
  666.     the packet they have received from A through B because that is not their
  667.     shortest path to A. Their shortest path is their direct link. 
  668.  
  669.  
  670. ----[  The Multicast Backbone (MBONE) 
  671.  
  672. It would be myopic to assume that every router on the internet supports
  673. multicast.  Thus, when a router needed to find the shortest path to a
  674. destination (for forwarding of a multicast packet) it could look in the
  675. unicast routing table.  Unfortunately (or fortunately depending on your
  676. perspective)  most routers on the Internet do not support multicast or do
  677. not have it enabled by default.  Therefore, until most routers support
  678. multicast, it has been "layered" over IP and tunneled from multicast router to
  679. multicast router (more specifically, the multicast header and data is
  680. encapsulated in a unicast IP header).  The tunnel (which bridges the gap of
  681. unicast only routers between multicast routers) informs each end that some
  682. packets will contain a multicast group in their payload.  This allows data to
  683. be routed by using unicast forwarding tables while at the same time preserving
  684. the integrity of the multicast group id. 
  685.  
  686. Because these multicast routers are not necessarily connected physically
  687. (though they are tunneled logically), they must be connected by a multicast
  688. routing protocol.  This is necessary because the closest path via multicast
  689. may not correspond to the shortest path over unicast only routers.  Distance
  690. Vector Multicast Routing Protocol (DVMRP) is an initial foray into this realm.
  691. DVMRP distributes "unicast" routes to facilitate the construction of shortest
  692. path trees.  DVMRP uses the flood and prune method discussed above to discover
  693. /maintain multicast trees.  There is also a link state foray into this arena.
  694. Multicast Open Shortest Path First (MOSPF) takes the LSP approach and
  695. calculates shortest absolute path.  One host off of a multicast router can
  696. request to be in a multicast group.  That router then distributes an LSP over
  697. the network.  Of course, MOSPF (being a link state protocol) runs into
  698. salability problems.  It is computationally expensive for a router to compute
  699. reachability information for each end node router.
  700.  
  701. Core based trees (CBT) are an attempt to alleviate the problems that DVMRP and
  702. MOSPF experience.  The concept is that multicast routers send join requests to
  703. core routers of arbitrary designation.  When a router learns of a host which
  704. wishes to join a specific multicast group, it forwards a packet to the core
  705. multicast router.  Every router along the way forwards the packet towards the
  706. core router and marks the interface on which the packet arrives so that it
  707. knows where to forward the multicast packets from the core.  This solves the
  708. problem of having to communicate topology among all of the endpoints.  The
  709. choice of a core multicast router is a non-trivial because all multicast
  710. traffic for multicast routers branching off of it _must_ pass through the core
  711. router.
  712.  
  713.   
  714. ----[  Protocol Independent Multicast
  715.  
  716. Protocol independent multicast (PIM).  Pim is a balance between flood and
  717. prune and CBT.  When there are many multicast routers on a given network, it
  718. is more efficient to use the flood-and-prune method.  This network environment
  719. is called "dense".  On the contrary, sparse mode defines networks where there
  720. are few multicast routers.  In sparse mode, it is more efficient to use CBT
  721. because the core router is not weighted in an environment when it 'polices'
  722. few multicast routers.  When most of network is comprised of multicast routers,
  723. it is not prudent to require all sessions to be coordinated (and routed
  724. through) a core.  Sparse mode PIM has been adapted from CBT to allow data to
  725. reach its destination via the core or through the shortest path tree.
  726. Currently, the operator must define whether groups are sparse or dense instead
  727. of leaving it up to the protocol.  cisco systems' implementation of pim also
  728. supports a middle ground called 'sparse-dense' mode.
  729.  
  730.  
  731. ----[  Border Gateway Protocol
  732.  
  733. There has been some mention of the Border Gateway Protocol (BGP) in this
  734. document.  BGP was groomed as the successor to the Exterior Gateway Protocol
  735. (EGP).  BGP is mainly an exterior routing protocol.  It is used to communicate
  736. with systems outside of the operator's control and both distribute and receive
  737. network layer reachability information (NRLI) from the neighboring routers.
  738. BGP must be a robust protocol which has the capability of quick convergence
  739. while at the same time, not being influenced by frequent shifts in topology.
  740. When you use BGP to receive routing information, you are depending on the
  741. other networks to distribute correct information to your network. 
  742.  
  743. A BGP speaking router communicates with its peers via TCP.  TCP over IP is a
  744. mechanism for guaranteeing the transmission of data over a best effort service
  745. at the IP layer.  The choice of TCP as the distribution mechanism for BGP
  746. information is a point of contention.  While TCP provides inherent checksums,
  747. acknowledgments, retransmissions and duplicate suppression mechanisms for
  748. received packets, it does not guarantee packet order or packet path.  This can
  749. lead to headaches for the router receiving this information.
  750.  
  751. BGP peers communicate with a variety of message formats.  BGP speakers use the
  752. OPEN message to establish a peering relationship with other speakers.  BGP
  753. speakers use the UPDATE message to transfer routing information between peers.
  754. Update information includes all routes and their associated attributes.
  755. KEEPALIVE messages assure that BGP peers are active.  NOTIFICATION messages
  756. inform peers of error conditions.
  757.  
  758.  
  759. ----[  BGP path selection
  760.  
  761. It is important that we understand the messages that constitute the Border
  762. Gateway Protocol, but we are still left with the question of how BGP works on
  763. the internet.  One important area of clarification is in the BGP path selection
  764. algorithm.  This algorithm is how BGP decides which route to prefer and
  765. attempt to install in the routing table.
  766.  
  767. This algorithm is employed when there are multiple paths to a destination.  As
  768. a failsafe, the first selection looks at the next hop and determines if it is
  769. accessible.  If the next hop is not accessible, it is important not to
  770. consider that route as a candidate path to a destination because all data sent
  771. to its next_hop will be blackholed.  The second selection mechanism is the
  772. weight of the route.  Weight is a proprietary implementation to cisco Systems
  773. routers and is analogous to local preference.  If two routes have different
  774. weights, the route with the largest weight is selected.  Notice that the
  775. selection mechanism is basically a logical if->then chain.  If candidate paths
  776. differ at a level of the selection algorithm, then the favorable path is
  777. selected and the algorithm ceases trying to decide which path to prefer.  The
  778. next level is the local_pref attribute.  This is a well known mandatory BGP
  779. attribute.  Much like weight, the path with the highest local_pref is
  780. preferred.  After local preference, the router selects the path that it
  781. originated.  If the router didn't originate the paths, then the path with the
  782. shortest AS_PATH length should be selected.  AS path length gauges the number
  783. of autonomous systems that this routing information has traveled through.
  784. The purpose of this selection relies in the assumption that the less ASNs the
  785. route has passed through, the closer the destination.  If all of the above
  786. attributes are identical, then prefer path origin in this fashion IGP > EGP >
  787. Incomplete.  If the path origins are the same, prefer the path with the lowest
  788. value MULTI_EXIT_DESCRIMINATOR (MED).  MEDs are commonly used to distinguish
  789. between multiple exit points to the same peer AS.  If none of these attributes
  790. are dissimilar, then prefer the path through the closest IGP neighbor.  If
  791. that fails, the tiebreaker is preferring the path with the lowest IP address
  792. specified in the BGP router-id section discussed above. 
  793.  
  794. This selection algorithm allows effective establishment of routing policy.  If
  795. I wanted to prefer routes from a certain AS over routes to another AS, I could
  796. establish a route-map at both entry points of external routing information and
  797. assign a higher LOCAL_PREF to the routes from the AS I want to favor.
  798. Unfortunately, this does not provide much granularity.  This means that all
  799. traffic will be routed to the favorable AS and does not allow us to balance
  800. the load over our multiple connections.  If you allow path selection to
  801. progress to the AS path length decision level, then you will get decent
  802. (though not 50-50) load balancing to destinations.  This of course is assuming
  803. that you have providers with comparable customer routes and connectivity.  If
  804. you have a DS3 to MCI and a DS3 to the local BFE provider, nearly all traffic
  805. will move out the MCI pipe if the BGP decision is allowed to progress down to
  806. the AS path length category.  At earlier selections, you can change the
  807. preference of routes by using AS path access lists to select routes based on
  808. as path regular expressions.  For example, if you wanted to select all routes
  809. that traversed UUnet and send them out your BFE provider, you could use a route
  810. map to match an AS path access list which contained _701_ and set the
  811. local_pref to 100 (or some value higher than the UUwho traversed paths from
  812. MCI).  This will force all traffic destined for UUwho to exit your AS over
  813. your BFE DS3.  While this affords you some granularity in load balancing, it
  814. is often not optimal.  Basically, you are forcing traffic out a path that it
  815. would not normally select.  If that BFE provider has many hops before it can
  816. reach UUnet, you are forcing the traffic you send out that link to traverse
  817. all of those hops and be subject to (possibly) more link congestion, latency,
  818. etc.
  819.  
  820. Routing policy is something that requires the tweaking of many knobs.  Much of
  821. the tweaking I have described above pertains to cisco Systems routers.  It is
  822. important to understand that you must think through routing policy before you
  823. implement it.  You must evaluate what load balancing you want, what traffic
  824. symmetry you want, and what general quality of service your traffic will
  825. receive because of your decisions.
  826.   
  827. For information more specific than this, read the BGP RFC or current BGPv4
  828. internet draft [1].
  829.   
  830.  
  831. ----[  Open Shortest Path First v2 (OSPFv2)
  832.  
  833. We are not going into great detail about OSPF.  It is a link state routing
  834. algorithm.  As noted above, link state algorithms route on flat space (no
  835. hierarchy).  OSPF is an improvement over the vanilla LS protocol because it
  836. provides areas of maintenance for hierarchy purposes.  Areas distribute full
  837. information internally by running a separate OSPF process with its area ID.
  838. Each router has an identical link state database with other routers within its
  839. area, but not with external routers.  Each area operates in an autonomous
  840. state and transfers inter-area information at junction routers called area
  841. border routers.  These routers are in two or more areas and help distribute
  842. information between these areas.  The router has separate link state databases
  843. for each area to which it is connected. 
  844.  
  845. OSPFv2's main advantage is that it supports Variable Length Subnet Masks
  846. (VLSM).  This means that a router can advertise reachability with more
  847. granularity than a scheme which advertised host reachability. Therefore, if
  848. the router can distribute packets to all hosts from 206.4.4.1 -> 206.4.5.254
  849. it advertises reachability to 206.4.4.0/23 instead of each classful network
  850. separately or each host separately.  This obviously saves immensely on link
  851. state database size and processing power required.
  852.  
  853. For information more specific than this, read the current OSPFv2 RFC or
  854. internet draft [2].
  855.   
  856.  
  857. ----[  References
  858.  
  859. [1] Rehkter, Y., Li, T., " A Border Gateway Protocol 4 (BGP-4)",
  860.             draft-ietf-idr-bgp4-07.txt, February 1998. 
  861.  
  862. [2] Moy, J., "OSPF Version 2", draft-ietf-ospf-vers2-02.txt,
  863.             January 1998. 
  864.  
  865. ----[  EOF
  866.  
  867.